package org.xqh.study.leetcode.bytedance;

import com.alibaba.fastjson.JSON;
import lombok.AllArgsConstructor;
import lombok.Builder;
import lombok.Data;
import lombok.NoArgsConstructor;
import scala.Int;

import java.util.*;

/**
 * @ClassName LargestRectangleArea
 * @Description 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 * <p>
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 * https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
 * @Author xuqianghui
 * @Date 2021/2/6 10:10
 * @Version 1.0
 */
public class LargestRectangleArea {

    public static void main(String[] args) {
//        int[] heights = {2,1,5,6,2,3};
//        int[] heights = {2, 1, 5, 5, 6, 1, 2};
//        int[] heights = {5, 7, 8, 1, 1, 4, 4, 6, 5, 0, 2};
////        int[] heights = {2, 1, 3};
////        int[] heights = {4,5,4,6,5,0,2};
////        int[] heights = {12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
//        System.out.println(largestRectangleArea77(heights));
        TestModel2 t = TestModel2.builder()
                .status(1)
                .name("afsdgg")
                .build();
        System.out.println(JSON.toJSONString(JSON.parseObject(JSON.toJSONString(t), TestModel1.class)));
    }

    @Data
    @Builder
    @AllArgsConstructor
    @NoArgsConstructor
    public static class TestModel1{
        private String name;
        private String status;
    }

    @Data
    @Builder
    @AllArgsConstructor
    @NoArgsConstructor
    public static class TestModel2{
        private Integer status;
        private String name;
    }

    public static void test(Integer a, String c){
        System.out.println(c);
    }

    public static void test(Integer a, String... b){
        System.out.println(JSON.toJSONString(b));
    }

    public static int largestRectangleArea77(int[] heights){
        int len = heights.length;
        if(len == 0){
            return 0;
        }
        if(len == 1){
            return heights[0];
        }

        Deque<Integer> deque = new ArrayDeque<>(len);
        //数组 前后 加入 两个元素 (哨兵) 不需要处理边界情况
        int[] newHeights = new int[len + 2];
        System.arraycopy(heights, 0, newHeights, 1, len);
        deque.offer(0);//左边元素
        int maxArea = 0;
        for(int i = 1; i < newHeights.length; i ++){
            while (!deque.isEmpty() && newHeights[deque.peekLast()] > newHeights[i]){
                int last = deque.pollLast();//取出栈顶
                //计算左边界 右边界 为i
                int left = deque.peekLast();
                int width = i - left -1;
                maxArea = Math.max(maxArea, width * newHeights[last]);
            }
            deque.offer(i);
        }
        return maxArea;
    }


    /**
     * 单调栈
     * @param heights
     * @return
     */
    public static int largestRectangleArea66(int[] heights){
        int maxArea = 0;
        int len = heights.length;
        Stack<Integer> stack = new Stack<>();
        int[] left = new int[len];// 正序循环 获取 栈中每个元素 的 左边元素下标
        int[] right = new int[len];// 逆序循环
        for(int i = 0; i < len ; i++){
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]){
                stack.pop();//出栈
            }
            left[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }

        stack.clear();

        for(int i = len - 1; i >= 0; i--){
            while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]){
                stack.pop();
            }
            right[i] = stack.isEmpty() ? len : stack.peek();
            stack.push(i);
        }
        /**
         *  数组 [4, 3, 1, 3, 5]
         *  哨兵 -1 (0, 1, 2, 3, 4) 5
         *  左侧边界 left = [-1, -1, -1, 2, 3]
         *  右侧边界 right = [1, 2, 5, 5, 5]
         */
        for(int k = 0; k < len; k++){
            int disLeft = left[k];
            int disRight = right[k];
            int width = disRight - disLeft - 1;
            maxArea = Math.max(maxArea, width * heights[k]);
        }

        return maxArea;
    }

    /**
     * 他人答案 0ms 耗时.
     * @param heights
     * @return
     */
    public static int largestRectangleArea00(int[] heights) {
        return maxArea(heights, 0, heights.length - 1);
    }

    public static int maxArea(int[] heights, int left, int right) {
        if (left > right){
            return 0;
        }
        if (left == right){
            return heights[left];
        }

        int minIndex = left;
        int minHeight = heights[left];
        // 判断是否单调递增，且记录最小高度
        boolean ordered = true;
        for (int i = left + 1; i <= right; i++) {
            if (ordered) {
                if (heights[i] >= heights[i - 1]) {
                    continue;
                } else {
                    ordered = false;
                }
            }
            if (heights[i] < minHeight) {
                minIndex = i;
                minHeight = heights[i];
            }
        }
        // 单调递增，则可以直接计算当前能够计算的最大面积
        if (ordered) {
            int width = right - left + 1;
            int maxArea = 0;
            for (int i = left; i <= right; i++) {
                maxArea = Math.max(maxArea, width * heights[i]);
                width--;
            }
            return maxArea;
        }
        // 无序，三个中求最大：最大宽度*最小高度；最矮柱左边能形成的最大面积；最矮柱右边能形成的最大面积
        return Math.max(
                minHeight * (right - left + 1), Math.max(
                        maxArea(heights, left, minIndex - 1),
                        maxArea(heights, minIndex + 1, right)
                )
        );
    }

    /**
     * 栈 + 哨兵 (数组 前后 加入 两位 不用处理 边缘情况)
     *
     * @param heights
     * @return
     */
    public static int largestRectangleArea(int[] heights) {
        int len = heights.length;//数组长度
        if (len == 0) {
            return 0;
        }

        if (len == 1) {
            return heights[0];
        }

        int[] nh = new int[len + 2];
        //复制 heights 到 nh
        System.arraycopy(heights, 0, nh, 1, len);
        int maxArea = 0;
        Deque<Integer> deque = new ArrayDeque<>();
        deque.offer(0);
        for (int i = 1; i < nh.length; i++) {
            //当前 栈顶 大于当前循环柱形 高度 的元素 要 弹出.
            while (nh[i] < nh[deque.peekLast()]) {
                int curIdx = deque.pollLast();
                int preLast = deque.peekLast();
                if(curIdx == preLast){// 如果 当前栈顶 和 前一个元素 高度一致 直接处理下一个
                    continue;
                }
                int curH = nh[curIdx];
                int width = i - preLast - 1;
                int curArea = curH * width;
                maxArea = Math.max(maxArea, curArea);
            }
            deque.offer(i);
        }
        return maxArea;
    }


    /**
     * 栈 存储
     *
     * @param heights
     * @return
     */
    public static int largestRectangleArea22(int[] heights) {
        Deque<Integer> deque = new ArrayDeque<>();//栈
        int maxArea = 0;
        for (int i = 0; i < heights.length; i++) {
            deque.offer(i);//将下标 入栈
            if (i == heights.length - 1 || heights[i] > heights[i + 1]) {
                //遍历到最后一位 或者 出现比当前矮的
                while (!deque.isEmpty()) {
                    Integer last = deque.peekLast();//
                    /**
                     * 当前栈顶元素  大于 当前序号+1 的元素 并且 大于 当前元素前一位
                     */
                    if (i != heights.length - 1 && heights[last] > heights[i + 1]) {
                        deque.pollLast();
                        Integer pre = deque.peekLast();
                        if (null != pre) {
                            if (heights[last] == heights[pre]) {
                                continue;
                            } else {
                                maxArea = Math.max(maxArea, (i - pre) * heights[last]);
                            }
                        } else {
                            if (last == 0) {
                                maxArea = Math.max(maxArea, (i - last + 1) * heights[last]);
                            } else {
                                //找到左边边界
                                int leftIdx = 0;
                                for (int j = last - 1; j >= 0; j--) {
                                    if (heights[last] > heights[j] || j == 0) {
                                        leftIdx = j;
                                        break;
                                    }
                                }
                                maxArea = Math.max(maxArea, (i - leftIdx + 1) * heights[last]);
                            }
                        }
                    } else {
                        break;
                    }
                }
            }
        }

        //处理剩下的元素
        while (!deque.isEmpty()) {
            int idx = deque.pollLast();
            int curHeight = heights[idx];
            if (!deque.isEmpty() && curHeight == heights[deque.peekLast()]) {
                continue;
            }
            int width = 1;
            if (idx > 0) {
                //向左查询
                l:
                for (int i = idx - 1; i >= 0; i--) {
                    if (heights[i] < curHeight) {
                        break l;
                    } else {
                        width++;
                    }
                }
            }

            if (idx < heights.length - 1) {
                //向右查询
                r:
                for (int i = idx + 1; i < heights.length; i++) {
                    if (heights[i] < curHeight) {
                        break r;
                    } else {
                        width++;
                    }
                }
            }
            maxArea = Math.max(maxArea, curHeight * width);
        }
        return maxArea;
    }

    /**
     * 暴力求解2
     *
     * @param heights
     * @return
     */
    public static int largestRectangleArea11(int[] heights) {
        int len = heights.length;
        int maxArea = 0;
        for (int i = 0; i < len; i++) {

            int curHeight = heights[i];
            int left = i;
            while (left > 0 && heights[left - 1] >= curHeight) {
                left--;
            }

            int right = i;
            while (right < len - 1 && heights[right + 1] >= curHeight) {
                right++;
            }

            int subLen = right - left + 1;
            maxArea = Math.max(maxArea, subLen * curHeight);

        }
        return maxArea;
    }

    /**
     * 暴力解法.  依次遍历每个 元素, 然后 元素向两边延伸 得到最大值
     *
     * @param heights
     * @return
     */
    public static int largestRectangleArea1(int[] heights) {

        int maxArea = 0;

        for (int i = 0; i < heights.length; i++) {
            int width = 1;//宽度
            int curHeight = heights[i];//当前 柱形高度
            //向左延伸
            if (i > 0) {
                l:
                for (int j = i - 1; j >= 0; j--) {
                    int il = heights[j];
                    if (il >= curHeight) {
                        width++;
                    } else {
                        break l;
                    }
                }
            }


            //向右延伸
            if (i < heights.length - 1) {
                r:
                for (int k = i + 1; k < heights.length; k++) {
                    int ir = heights[k];
                    if (ir >= curHeight) {
                        width++;
                    } else {
                        break r;
                    }
                }
            }
            maxArea = Math.max(maxArea, curHeight * width);
        }


        return maxArea;
    }


    /**
     * 滑动窗口 + 优先队列 运行超时
     *
     * @param heights
     * @return
     */
    public static int largestRectangleArea2(int[] heights) {
        int maxArea = 0;

        for (int len = 1; len <= heights.length; len++) {
            int mHeight = 0;
            PriorityQueue<Integer> pQueue = new PriorityQueue<>(new Comparator<Integer>() {
                @Override
                public int compare(Integer n1, Integer n2) {
                    return n1.compareTo(n2);
                }
            });
            for (int i = 0; i < len; i++) {
                pQueue.offer(heights[i]);
            }
            mHeight = pQueue.peek();//
            Map<Integer, Integer> delMap = new HashMap<>();
            //窗口长度 len 从左向右滑动
            for (int i = 1; i <= heights.length - len; i++) {
                int remove = heights[i - 1];
                delMap.put(remove, delMap.getOrDefault(remove, 0) + 1);
                //取出移除的堆顶元素
                while (!pQueue.isEmpty()) {
                    Integer top = pQueue.peek();
                    if (delMap.containsKey(top)) {
                        if (delMap.get(top) == 1) {
                            delMap.remove(top);
                        } else {
                            delMap.put(top, delMap.get(top) - 1);
                        }
                        pQueue.poll();
                    } else {
                        break;
                    }
                }
                pQueue.offer(heights[i + len - 1]);
                Integer top = pQueue.peek();
                if (mHeight < top) {
                    mHeight = top;
                }
            }
            int areaItem = len * mHeight;
            maxArea = Math.max(maxArea, areaItem);
        }

        return maxArea;
    }
}
